package tree;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/lh5kuh/
public class 寻找二叉树的最近公共祖先 {
      public class TreeNode {
      int val;
      TreeNode left;
     TreeNode right;
      TreeNode(int x) { val = x; }
  }
  //先序遍历
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || root == p || root == q) return root;
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            TreeNode right= lowestCommonAncestor(root.right,p,q);
            if(left == null && right == null) return null;
            if(left == null) return right;
            if(right == null)return left;
            return root;
        }
    }
}
